package tree;

/**
 * leet-code(208) 前缀树
 *
 * @author Ringo
 * @date 2021/8/30 17:50
 */
public class Trie {

    private Node root;

    public Trie() {
        root = Node.createNode().children(new Node[26]).isEnd(false);
    }

    public void insert(String word) {
        Node node = root;
        int n = word.length();
        for (int i = 0; i < n; ++i) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null)
                node.children[index] = Node.createNode();
            node = node.children[index];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        Node node = searchPrefix(word);
        return node != null && node.isEnd;
    }


    private Node searchPrefix(String prefix) {
        Node node = root;
        int n = prefix.length();
        for (int i = 0; i < n; ++i) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null)
                return null;
            node = node.children[index];
        }
        return node;
    }

    /**
     * 定义结点
     */
    private static class Node {
        private Node[] children;
        private boolean isEnd;

        public static Node createNode() {
            return new Node();
        }

        public Node children(Node[] children) {
            this.children = children;
            return this;
        }

        public Node isEnd(boolean isEnd) {
            this.isEnd = isEnd;
            return this;
        }
    }

}
